package org.langqiao.algorithm;
//给定33个数 从33个中选6个（可以重复） 加和等于150 ,统计有多少种排列方法
public class Shu33_6 {
	public static void main(String[] args)throws Exception
	{
		int[] a={20,15,30,9,10,23,33,43,34,21,45,67,58,2,6,8,80,90,70};
		think(0,150,a,0,new int[6]);
		System.out.println("组合的个数为："+cal(1,33,6,150));
	}
	//i为当前数组考虑装载的数组下标，totalNow当前容量，src是数据源，size当前是第几个数，result是结果集
	static void think(int i,int totalNow,int[] src,int size,int[] result)
	{
	    if(size==5)	
	    {
	    	if(totalNow==src[i])
	    	{
	    		result[size]=src[i];
	    		for(int k=0;k<result.length;k++)
	    		{
	    			System.out.print(result[k]+" ");
	    		}
	    		System.out.println();//换行
	    	}
	    	return;//已经装载了6次
	    }
	    if(totalNow<src[i])
	    {
	    	return;//不能在装了，装了就超了
	    }
	    int[] r=new int[6];
	    System.arraycopy(result,0,r,0,6);
	    for(;i<src.length;i++)
	    {
	    	r[size]=src[i];
	    	think(i,totalNow-src[i],src,size+1,r);
	    }
	}
	public static int cal(int from,int to,int count,int sum)
	{
		if(count==0)return sum==0?1:0;
		if(sum<from*count||count>to+1-from)return 0;
		return cal(from+1,to,count-1,sum-from)+cal(from+1,to,count,sum);
	}

}
